#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if (nums.size() <= 1) return nums;
        vector<int>sizes(nums.size(), 0);
        sort(nums.begin(), nums.end(), less<int>());

        int index = 0;
        int maxSize = 0;

        for (int i = 0; i < nums.size(); ++i) {
            int maxSubSize = 0;
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0 && maxSubSize < sizes[j])
                    maxSubSize = sizes[j];
            }
            sizes[i] = maxSubSize + 1;
            if (maxSize < sizes[i]) {
                maxSize = sizes[i];
                index = i;
            }
            
        }
        vector<int>res;
        for (int i = index; i >= 0; --i) {
            if (nums[index] % nums[i] == 0 && sizes[i] == maxSize) {
                res.push_back(nums[i]);
                --maxSize;
            }
        }

        reverse(res.begin(), res.end());
        return res;
    }
};


